package com.lw.leetcode.bingChaJi.b;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * bingchaji
 * 1722. 执行交换操作后的最小汉明距离
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/25 11:21
 */
public class MinimumHammingDistance {

    public static void main(String[] args) {
        MinimumHammingDistance test = new MinimumHammingDistance();

        // 1
//        int[] source = {1, 2, 3, 4};
//        int[] target = {2, 1, 4, 5};
//        int[][] allowedSwaps = {{0, 1}, {2, 3}};

        // 2
//        int[] source = {1, 2, 3, 4};
//        int[] target = {1, 3, 2, 4};
//        int[][] allowedSwaps = {};

        // 0
        int[] source = {5, 1, 2, 4, 3};
        int[] target = {1, 5, 4, 2, 3};
        int[][] allowedSwaps = {{0, 4}, {4, 2}, {1, 3}, {1, 4}};

        int i = test.minimumHammingDistance(source, target, allowedSwaps);
        System.out.println(i);

    }


    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        int length = source.length;
        int[] arr = new int[length];
        Arrays.fill(arr, -1);
        for (int[] allowedSwap : allowedSwaps) {
            int a = find(arr, allowedSwap[0]);
            int b = find(arr, allowedSwap[1]);
            if (a != b) {
                if (a < b) {
                    arr[b] = a;
                    arr[allowedSwap[1]] = a;
                } else {
                    arr[a] = b;
                    arr[allowedSwap[0]] = b;
                }
            }
        }
        Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
        for (int i = 0; i < length; i++) {
            int v = arr[i];
            if (v != -1) {
                while (v != arr[v]) {
                    v = arr[v];
                }
                arr[i] = v;
                Map<Integer, Integer> m = map.computeIfAbsent(v, item -> new HashMap<>());
                m.merge(source[i], 1, (a, b) -> a + b);
            }
        }
        int count = length;
        for (int i = 0; i < length; i++) {
            int s = source[i];
            int t = target[i];
            if (map.containsKey(arr[i])) {
                Map<Integer, Integer> m = map.get(arr[i]);
                int c = m.getOrDefault(t, 0);
                if (c > 0) {
                    count--;
                    m.put(t, c - 1);
                }
            } else {
                if (s == t) {
                    count--;
                }
            }
        }
        return count;
    }

    private int find(int[] arr, int t) {
        int i = arr[t];
        if (i == -1 || i == t) {
            arr[t] = t;
            return t;
        }
        int n = find(arr, i);
        arr[t] = n;
        return n;
    }

}
